/**
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * 输入: [1,2,3]
 输出:
 [
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
 ]
 */
// TODO:全排列
const arr = [1, 2, 3]
const strArr = ['a', 'b', 'c']

function permute(arr) {
    let res = []

    DFS([])

    function DFS(nums) {
        if (nums.length === arr.length) {
            res.push([...nums]);
            return
        }

        for (let i = 0; i < arr.length; i++) {
            if (nums.includes(arr[i])) {
                continue;
            }
            nums.push(arr[i])
            DFS(nums)
            nums.pop()
        }
    }

    return res;
}

permute(arr)

function permuteV2(arr) {
    const res = []

    function DFS(nums) {
        if (nums.length === arr.length) {
            res.push([...nums])
            // return;
        }
        for (let i = 0; i < arr.length; i++) {
            if (nums.includes(arr[i])) {
                continue;
            }
            nums.push(arr[i])
            DFS(nums)
            nums.pop()
        }
    }

    DFS([])
    return res;
}

// console.log(permuteV2(arr));
